package com.example.startup.sort

import com.example.startup.StartUp
import java.util.ArrayDeque


typealias key = Class<out StartUp<*>>

object TopologySort {

    public fun sort(startList: List<StartUp<*>>): StartUpSortStore {
        // 入度表
        val inDegree = HashMap<key, Int>()
        // 0度表
        val zeroDegree = ArrayDeque<key>()
        // 任务表
        val startUpMap = HashMap<key, StartUp<*>>()
        //  任务依赖表
        val startUpDependencies = HashMap<key, ArrayList<key>>()

        // 找出图中任务为0的节点
        for (startUp in startList) {
            startUpMap[startUp::class.java] = startUp
            // 记录每个任务的入度数
            val dependenciesCount = startUp.getDependenciesCount()
            inDegree[startUp::class.java] = dependenciesCount
            if (dependenciesCount == 0) {
                zeroDegree.add(startUp::class.java)
            } else {
                startUp.dependencies()?.let {
                    // 比如依赖于任务1的有2和3
                    // 底下这行代码是 错误的 <任务2> = [任务1]
                    //   startUpDependencies[startUp::class.java] = it as ArrayList<key>
                    // 正确的应该是 <任务1> = [任务2,任务3]
                    for (dependency in it) {
                        var children = startUpDependencies[dependency]
                        if (children == null) {
                            children = ArrayList()
                            startUpDependencies[dependency] = children
                        }
                        children.add(startUp::class.java)
                    }
                }
            }
        }


        // 删除0度节点 并更新全图，最后完成排序
        val result = ArrayList<StartUp<*>>()
        while (!zeroDegree.isEmpty()){
            val zero = zeroDegree.poll()?:continue
            startUpMap[zero]?.let {
                result.add(it)
            }
            // 删除此入度为0的任务
            if (startUpDependencies.contains(zero)) {
                val classes = startUpDependencies[zero]?: arrayListOf()
                for (clazz in classes){
                    val count = inDegree[clazz]?:0
                    inDegree[clazz] = count - 1
                    if (inDegree[clazz] == 0){
                        zeroDegree.add(clazz)
                    }
                }
            }
        }

        return StartUpSortStore(result,startUpMap,startUpDependencies)

    }

}


